package main

import (
	"fmt"
)

/*
稠密图 - 邻接矩阵
时间复杂度：
优点：
缺点：

*/

type denseGraph struct {
	n int
	m int
	directed bool
	g [][]bool
}

func (dg *denseGraph) init(n int, directed bool) {
	dg.n = n
	dg.m = 0
	dg.directed = false

	dg.g = make([][]bool, n)
	for i := range dg.g {
		dg.g[i] = make([]bool, n)
	}
}

func (dg *denseGraph) V() int {
	return dg.n
}

func (dg *denseGraph) E() int {
	return dg.m
}

func (dg *denseGraph) addEdge(v int, w int) {

	if dg.hasEdge(v, w) {
		return
	}

	dg.g[v][w] = true

	if dg.directed {
		dg.g[w][v] = true
	}

	dg.m++
}

func (dg *denseGraph) hasEdge(v int, w int) bool {

	return dg.g[v][w]
}

func (dg *denseGraph) show() {

	for i, v := range dg.g {

		fmt.Print(i)
		for j, x := range v {
			if x {
				fmt.Print(" ", j)
			}

		}
		fmt.Println()

	}
}



func main()  {

	data := [][]int {
		{13, 13},
		{0, 5},
		{4, 3},
		{0, 1},
		{9, 12},
		{6, 4},
		{5, 4},
		{0, 2},
		{11, 12},
		{9, 10},
		{0, 6},
		{7, 8},
		{9, 11},
		{5, 3},

	}


	dg := new(denseGraph)

	n := data[0][0]
	dg.init(n, true)

	for i := 1; i < n; i++ {

		dg.addEdge(data[i][0], data[i][1]);
	}

	//n := 5
	//dg.init(n, true)
	//
	//rand.Seed(time.Now().Unix())
	//
	//for i := 0; i < n; i++ {
	//	a := rand.Intn(100) % n
	//	b := rand.Intn(100) % n
	//	dg.addEdge(a, b);
	//}

	dg.show()
}
